Balance and Transitivity

SNA Week 5

Matt Pietryka

Calculating Bonacich Power Centrality

\[ c_i(\alpha, \beta) = \sum_j (\alpha + \beta c_j)s_{ij} \]

where:

  • \(c_j\) is node \(j\)’s score
  • \(s_{ij}\) is cell \(i,j\) in the sociomatrix
  • \(\alpha\) a scaling parameter
  • \(\beta\) determines the role of node \(j\)’s score

# CREATE RANDOM NETWORK 
N_NODES <- 20
set.seed(2)
er_net <- erdos.renyi.game(N_NODES, p = 0.2, directed = FALSE)
er_net <- er_net  %>%  add_layout_(with_fr())

# CALCULATE POWER CENTRALITY
library(igraph)
power_centrality(er_net,  exponent = -1)
##  [1]  0.48099187  1.60330622  0.18037195  0.56115718  1.36281029
##  [6]  0.96198373  0.22045461  0.98202506  1.96405012 -0.10020664
## [11]  0.26053726 -0.04008266  1.44297560  0.46095054  1.66343020
## [16]  0.06012398  0.74152913 -0.78161178  1.20247966  1.20247966
power_centrality(er_net,  exponent = 1)
##  [1] -0.7290826 -0.7290826 -0.5468120  0.1822707 -0.3645413 -1.2758946
##  [7]  0.3645413  0.0000000 -0.9113533 -0.5468120 -0.9113533 -1.6404359
## [13] -1.2758946 -0.1822707 -0.3645413 -2.1872478 -0.3645413 -0.7290826
## [19] -1.4581652 -1.6404359

Note: Node labels represent power rank; Node opacity indicates relative differences in power

Balance

Balance measures help us understand triples in signed networks

  • triples are triads of actors
  • Signed networks denote relationships of opposing valences

Signed networks denote relationships of opposing valences

  • edges in signed networks typically have one of two values: +1 or -1
    • friend vs enemy
    • agree vs disagree
    • love vs hate
    • ally vs opponent

All possible connected triples

Creating example networks

library(igraph)
library(tidyverse)

N_NODES <- 8

# ------- CREATE BALANCED NETWORK  ---------------- #

# DATA ON EDGES
edge_data <- expand.grid(a = 1:N_NODES, b = 1:N_NODES)   %>%
  filter(a != b)  %>%
  mutate(a_group = ifelse(a < 6, 1, 2))  %>%
  mutate(b_group = ifelse(b < 6, 1, 2))  %>%
  mutate(weight = ifelse(a_group == b_group, 1, -1))  %>%
  mutate(sign = ifelse(a_group == b_group, "+", "-"))

Creating example networks

edge_vector <- rbind(edge_data[,1], edge_data[,2])  %>% c()
balanced_net <- graph(edges = edge_vector, n = N_NODES, directed = FALSE)

# VERTEX ATTRIBUTES
  V(balanced_net)$color        <- "grey50"
  V(balanced_net)$size         <- 35
  V(balanced_net)$label.cex    <- 3
  V(balanced_net)$label.font   <- 2
  V(balanced_net)$label.family <- "sans"
  V(balanced_net)$label.color  <- "white"
  V(balanced_net)$frame.color  <- NA

Creating example networks

# EDGE ATTRIBUTES
  E(balanced_net)$weight <- edge_data$weight
  E(balanced_net)$sign   <- edge_data$sign
  E(balanced_net)$color  <- ifelse(edge_data$weight > 0, 
                                  "grey80", 
                                  shade_B0)
  E(balanced_net)$lty    <- ifelse(E(balanced_net)$weight > 0, 
                                1, 
                                2)
  E(balanced_net)$width  <- 2

Creating example networks

# ------- CREATE UNBALANCED NETWORK  ---------------- #

set.seed(400)
unbalanced_net <- graph(edges = edge_vector, 
                         n = N_NODES, 
                         directed = FALSE) 
# VERTEX ATTRIBUTES
  V(unbalanced_net)$color        <- "grey30"
  V(unbalanced_net)$size         <- 35
  V(unbalanced_net)$label.cex    <- 3
  V(unbalanced_net)$label.font   <- 2
  V(unbalanced_net)$label.family <- "sans"
  V(unbalanced_net)$label.color  <- "white"
  V(unbalanced_net)$frame.color  <- NA

Creating example networks

# EDGE ATTRIBUTES
  E(unbalanced_net)$weight <- sample(c(-1,1), 
                                      ecount(unbalanced_net),
                                      replace = TRUE)
  E(unbalanced_net)$sign   <- ifelse(E(unbalanced_net)$weight > 0, 
                                     "+", 
                                     "-")
  E(unbalanced_net)$color  <- ifelse(E(unbalanced_net)$weight > 0, 
                                    "grey80", 
                                    shade_B0)
  E(unbalanced_net)$lty    <- ifelse(E(unbalanced_net)$weight > 0, 
                                  1, 
                                  2)
  E(unbalanced_net)$width  <- 2

Creating example networks

#=============================================
#   CREATE PLOTS
#=============================================

# LAYOUTS
balanced_lay_circle   <- layout_(balanced_net, in_circle())
unbalanced_lay_circle <- layout_(unbalanced_net, in_circle())

Creating example networks

# PLOTTING PREFERENCES
par(mar = c(0, 0, 0, 0)) # NO MARGINS ON ANY SIDE
par(mfrow = c(1, 2)) #  ONE ROW AND TWO COLUMNS
par(cex.main = 4) # PLOT TITLE SIZE

# ------- PLOT WITHOUT HIGHLIGHTS  ---------------- #
plot(balanced_net, layout = balanced_lay_circle)
title(main = "A", line = -4)
plot(unbalanced_net, layout = unbalanced_lay_circle)
title(main = "B", line = -4)

What differences do you see?

What differences do you see?

Creating example networks

# FIND COMMUNITIES
balanced_coms   <- spinglass.community(balanced_net, 
                                       implementation = "neg")
unbalanced_coms <- spinglass.community(unbalanced_net, 
                                       implementation = "neg")

# PLOTTING PREFERENCES
par(mar = c(0, 0, 0, 0)) # NO MARGINS ON ANY SIDE
par(mfrow = c(1, 2)) #  ONE ROW AND TWO COLUMNS
par(cex.main = 4) # PLOT TITLE SIZE

# ------- PLOT WITH HIGHLIGHTS  ---------------- #
plot(balanced_net,  mark.groups = balanced_coms,
     layout = balanced_lay_circle,
     mark.border = NA,
     mark.col = c(shade_A1,shade_C1))
title(main = "A", line = -4)

plot(unbalanced_net,  mark.groups = unbalanced_coms,
     layout = unbalanced_lay_circle,
     mark.border = NA,
     mark.col = adjustcolor(c(shade_A2, shade_B2, shade_C2), 0.8))
title(main = "B", line = -4)

#=============================================
#   FUNCTION TO FIND SIGN OF EACH TRIPLE IN NETWORK
# (ASSUMES SIGN OF TIES IS STORED IN 'E(g)$weight')
#=============================================
triple_signs <- function(net) {
  #FIND IDS OF ALL NODES IN EACH TRIPLE
    triple_ids <- combn(1:vcount(net), 3)
  #FOR EACH TRIPLE ...
  apply(triple_ids, 2,  function(x) {
    # ... IDENTIFY ITS EDGES
    edges <- E(net) [ x %--% x ]
    # ... IDENTIFY EDGE VALUES
    weights <- E(net)[edges]$weight
    # ... FIND PRODUCT OF ITS VALUES
    sign <- prod(weights)
    # RETURN THE SIGN OF EACH VALUE
    return(sign)
  })
}

triple_signs(balanced_net)  %>% table()
## .
##  1 
## 56
triple_signs(unbalanced_net) %>% table()
## .
## -1  1 
## 36 20

Balance of nodes: all cycles containing node \(i\) are positive

  • Also known as local balance
  • Cycles are paths originating and returning to the same node
  • The sign of a cycle is the product of its links

#=============================================
#   FUNCTION TO FIND LOCAL BALANCE FOR EACH NODE 
# (ASSUMES COMPLETE GRAPH)
# (ASSUMES SIGN OF TIES IS STORED IN 'E(g)$weight')
#=============================================
local_balance <- function(net) {
 # FIND ALL TRIPLES IN 'g'
  triple_ids <- combn(1:vcount(net), 3)
 # INDICATE RELEVANT TRIPLES FOR EACH NODE
  rel_triple <- apply(triple_ids, 2, function(x) V(net) %in% x)
 # FIND SIGN OF EACH TRIPLE
  signs <- triple_signs(net)
 # TOTAL TRIPLES NODE i IS INVOLVED IN
  total_trips <- apply(rel_triple, 1,sum)
 # TOTAL NUMBER OF POSITIVE TRIPLES NODE i IS INVOLVED IN
  pos_trips <- sapply(V(net), function(x)  sum(signs[rel_triple[x, ]] > 0))
 # LOCAL BALANCE
  return(pos_trips/total_trips)
}

local_balance(balanced_net)  
## [1] 1 1 1 1 1 1 1 1
local_balance(unbalanced_net)
## [1] 0.3333333 0.2380952 0.5714286 0.5238095 0.2857143 0.2380952 0.3809524
## [8] 0.2857143

Balance of network: network is balanced iff all triangles are balanced

Balance of network: network is balanced iff all triangles are balanced

Degree of balance in network: the proportion of all triangles that are positive

\[ B = \frac{C^+}{(C^+ + C^-)} \]

Where:

  • \(C^+\) = number of positive triangles
  • \(C^-\) number of negative triangles

\[ B = \frac{C^+}{(C^+ + C^-)} \]

#=============================================
#   FUNCTION TO FIND GLOBAL NETWORK BALANCE 
# (ASSUMES SIGN OF TIES IS STORED IN 'E(g)$weight')
#=============================================

network_balance <- function(g) {
  # FIND ALL TRIPLES IN 'g'
  triples <- combn(1:vcount(g), 3)
  # SET COUNTERS TO ZERO
  good <- bad <- 0
  # FOR EACH TRIPLE, DETERMINE IF BALANCED
  for (t in 1:ncol(triples)) {
    # THE FOCAL TRIPLE
    tri <- triples[,t]
    # FIND ALL EDGES IN FOCAL TRIPLE
    edges <- E(g) [ tri %--% tri ]
    if (length(unique(get.edges(g, edges))) < 3) { next }
    if (prod(E(g)[edges]$weight) > 0) {
      good <- good + 1 # IF PRODUCT IS POSITIVE INCREMENT UP
    } else {
      bad <- bad + 1   # IF PRODUCT IS NEGATIVE INCREMENT UP
    }
  }
  # CALCULATE GLOBAL BALANCE
  b <- good/(good + bad)
  # IS THE NETWORK BALANCED?
  is_balanced <- ifelse(b == 1, TRUE, FALSE)
  # RETURN RESULTS AS LIST
  list(is_balanced, n_balanced = good, n_unbalanced = bad, global_balance = b)
}

network_balance(balanced_net)  
## [[1]]
## [1] TRUE
## 
## $n_balanced
## [1] 56
## 
## $n_unbalanced
## [1] 0
## 
## $global_balance
## [1] 1
network_balance(unbalanced_net)
## [[1]]
## [1] FALSE
## 
## $n_balanced
## [1] 20
## 
## $n_unbalanced
## [1] 36
## 
## $global_balance
## [1] 0.3571429
local_balance(unbalanced_net)  %>% mean()
## [1] 0.3571429

Degree of balance in network: the proportion of all triangles that are positive

# FIND BALANCE LEVEL
network_balance(g)
## [[1]]
## [1] FALSE
## 
## $n_balanced
## [1] 20
## 
## $n_unbalanced
## [1] 20
## 
## $global_balance
## [1] 0.5

Transitivity

The Transitivity of a triad means that when there is a tie from \(i\) to \(j\), and also from \(j\) to \(k\), then there is also a tie from \(i\) to \(k\)

  • If \(i \nrightarrow j\) and/or \(j \nrightarrow k\), then the triad is vacuously transitive
  • neither transitive nor intransitive

If \(S^2_{ik} \geq 1\), the relation is transitive if \(s_{ik} = 1\)

Transitivity of the network given by the Global Clustering Coefficient C

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}}\]

  • Closed triples are three nodes connected by three undirected ties
  • Open triples are three nodes connected by two undirected ties
  • Gives the probability that two nodes with a common partner are adjacent to each other

# CREATE NETWORK

N_NODES <- 4
edges <- c(1,2, 1,3, 2,3, 3, 4)
trans_net <- graph(edges = edges, n = N_NODES, directed = FALSE)  %>% 
  set_vertex_attr("name", value = letters[1:N_NODES])



#PLOT NETWORK
set.seed(1)
plot(trans_net, 
     vertex.size = 60,
     vertex.frame.color = NA,
     vertex.color = shade_C0, 
     vertex.label.color = "white",
     vertex.label.cex = 5,
     vertex.label.family = "sans",
     edge.width = 3)

Transitivity of the network given by the Global Clustering Coefficient C

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}}\]

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}} \]

# NETWORK AS A SOCIOMATRIX
trans_socio <- get.adjacency(trans_net, sparse = FALSE)

# SECOND- AND THIRD-ORDER SOCIOMATRICES
p2 <- trans_socio %*% trans_socio
p3 <- p2 %*% trans_socio


# PATHS OF LENGTH TWO (IGNORING PATHS TO SELF)
diag(p2) <- 0
p2_sum <- sum(p2)
p2_sum
## [1] 10
# CYCLES OF LENGTH THREE 
c3_sum <- diag(p3)   %>% sum()
c3_sum
## [1] 6
# GLOBAL CLUSTERING
c3_sum/p2_sum
## [1] 0.6

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}} \]

# GLOBAL CLUSTERING BY HAND
c3_sum/p2_sum
## [1] 0.6
# GLOBAL CLUSTERING IN IGRAPH 
transitivity(trans_net, type = "globalundirected")
## [1] 0.6

RANDOM_N <- 50

# CREATE AN ERDOS-RENYI SMALL WORLD NETWORK
set.seed(1)
er_net <- erdos.renyi.game(RANDOM_N, p = 0.1, directed = FALSE)
edge_density(er_net)
## [1] 0.09877551
transitivity(er_net, type = "globalundirected")
## [1] 0.1125

RANDOM_N <- 50

# CREATE A WATTS-STROGATZ SMALL WORLD NETWORK
set.seed(1)
ws_net <- sample_smallworld(1, RANDOM_N, 2, 0.10) 
edge_density(ws_net)
## [1] 0.08163265
transitivity(ws_net, type = "globalundirected")
## [1] 0.245283

Transitivity of the nodes given by the Local Clustering Coefficient \(c_i\)

\[ c_i = \frac{\text{number of ties in i's neighborhood}}{\text{possible number of ties in i's neighborhood| neighborhood size }} \]

\[ c_i = \frac{\text{number of ties in i's neighborhood}}{\text{possible number of ties in i's neighborhood| neighborhood size }} \]

# BY HAND
lapply(1:N_NODES,  function(x){
  # FIND ONE-STEP NEIGHBORHOODS
  local_ids <- which(trans_socio[x, ] == 1)
  nhood   <- trans_socio[local_ids, local_ids]
  # TOTAL NUMBER OF NEIGHBORS
  n_neighbors <- nrow(nhood)
  # MAXIMUM NUMBER OF TIES IN NEIGHBORHOOD
  nhood_max   <- n_neighbors * (n_neighbors - 1)
  # LOCAL CLUSTERING = (NUM. TIES/MAX POSSIBLE NUM. TIES)
  sum(nhood)/nhood_max
  }) 
## [[1]]
## [1] 1
## 
## [[2]]
## [1] 1
## 
## [[3]]
## [1] 0.3333333
## 
## [[4]]
## numeric(0)

\[ c_i = \frac{\text{number of ties in i's neighborhood}}{\text{possible number of ties in i's neighborhood| neighborhood size }} \]

# IN IGRAPH
transitivity(trans_net, type = "localundirected")
## [1] 1.0000000 1.0000000 0.3333333       NaN